package com.kevin.Code.Stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author Vinlee Xiao
 * @Classname LargestRectangleinHistogram
 * @Description Leetcode 84 柱状图中最大的矩形 hot100 困难
 * @Date 2021/11/28 19:39
 * @Version 1.0
 */
public class LargestRectangleinHistogram {


    /**
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {

        int len = heights.length;

        if (len == 0) {
            return 0;
        }

        if (len == 1) {
            return heights[0];
        }
        int res = 0;
        Deque<Integer> deque = new ArrayDeque<>(len);
        int width = 0;
        int curHeight = 0;
        for (int i = 0; i < len; i++) {

            while (!deque.isEmpty() && heights[i] < heights[deque.peekLast()]) {

                //
                curHeight = heights[deque.pollLast()];
                //排除特殊情况 前一个数和当前相同
                while (!deque.isEmpty() && curHeight == heights[deque.peekLast()]) {
                    deque.peekLast();
                }

                if (deque.isEmpty()) {
                    width = i;
                } else {
                    width = i - deque.peekLast() - 1;
                }
                res = Math.max(res, width * curHeight);
            }

            deque.addLast(i);
        }
        //当栈里面还有元素
        while (!deque.isEmpty()) {

            //
            curHeight = heights[deque.pollLast()];
            //排除特殊情况 前一个数和当前相同
            while (!deque.isEmpty() && curHeight == heights[deque.peekLast()]) {
                deque.pollLast();
            }

            if (deque.isEmpty()) {
                width = len;
            } else {
                width = len - deque.peekLast() - 1;
            }

            res = Math.max(res, width * curHeight);
        }

        return res;
    }


}
